/**
 * 
 */
package array.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class Triangle {

	/**
	Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

	For example, given the following triangle

	[
	 [2],
	[3,4],
	[6,5,7],
	[4,1,8,3]
	]
	The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
	Note:
	Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
	 */
	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {

		if (triangle == null || triangle.isEmpty()) {
			return 0;
		}

		ArrayList<Integer> buffer = new ArrayList<Integer>(triangle
		        .get(triangle.size() - 1));
		for (int i = triangle.size() - 2; i >= 0; i--) {
			ArrayList<Integer> currRow = triangle.get(i);
			for (int j = 0; j < currRow.size(); j++) {
				buffer.set(j, currRow.get(j)
				        + Math.min(buffer.get(j), buffer.get(j + 1)));
			}
		}

		return buffer.get(0);
	}

	/**
	 * 
	 */
	public Triangle() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
